package sort;

import java.util.Arrays;

public class ShellSort2 {
    public static void main(String[] args) {
        int[] a = {2,6,1,5,8,3,2,6,8,1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));

        //Arrays.sort(new int[]{});//快速排序
        //Arrays.sort(new Object[]{});//归并排序
    }
    /*
        1. gap循环从 a.length/2 到 1，修改 gap /= 2
        2. i循环，从gap递增到末尾
        3. 取出i位置的值存到临时变量
        4. j从i-gap位置开始，向前 -=gap，j的范围>=gap
        5. 如果j-gap位置的值大，将这个值复制到j位置
           否则，结束j循环
        6. j循环结束后，临时值放到j位置
     */
    private static void sort(int[] a) {
        for (int gap = a.length/2; gap >= 1; gap /= 2) {
            // 插入排序
            for (int i = gap; i < a.length; i++) {
                for (int j = i-gap; j >=0 ; j-=gap) {
                    if (a[j]>a[j+gap]){
                        int tem = a[j];
                        a[j] = a[j+gap];
                        a[j+gap] = tem;
                    }
                }
            }

        }

    }
}
